The invention relates to data processing systems using vector processing and Very Long Instruction Word (VLIW) architecture, more particularly to variable length encoding.
A frame of image can be represented by a matrix of points referred to as pixels. Each pixel has one or more attributes representing the color associated with the pixel. Video streams are represented by consecutive frames of images. To efficiently store or transport image and video information, it is necessary to use data compression technologies to compress the data representing the attributes of each pixel of each frame of the images.
Various standards have been developed for representing image or video information in compressed formats, which includes Digital Video (DV) formats, MPEG2 or MPEG4 fomiats from Moving Picture Expert Group, ITU standards (e.g., H.261 or H.263) from International Telecomunication Union, JPEG formats from Joint Photographic Expert Group, and others.
Many standard formats (e.g., DV, MPEG2 or MPEG4, H.261 or H.263) use block based transform coding techniques. For example, 8xc3x978 two-dimensional blocks of pixels are transformed into frequency domain using Forward Discrete Cosine Transformation (FDCT). The transformed coefficients are further quantized and coded using zero run length encoding and variable length encoding.
Zero run length encoding is a technique for converting a list of elements into an equivalent string of run-level pairs, where each non-zero eleiment (level) in the list is associated with a zero run value (run) which represents the number of consecutive elements of zero immediately preceding the corrusponding non-zero element in the list. After zero run length encoding, strings of zeros in the list are represented by zero run values associated with non-zero elements. For example, the non-zero elements and their associated zero run values can be interleaived into a new list to represent the original list of elements with strings of zeros.
Variable length coding is a coding technique often used for lossless data compressing. Codes of shorter lengths (e.g., Huffman codewords) are assigned to frequently occurring fixed-length data (or symbols) to achieve data compression. Variable length encoding is widely used in compression video data.
After the Forward Discrete Cosine Transformation and quantization, the frequency coefficients are typically reordered in a zigzag order so that the zero coefilcients are grouped together in a list of coefficients, which can be mnore effectively encoded using a zero run length encoding technique. The energy of a block of pixels representing a block of image is typically concentrated in the lower frequency area. When the coefficients are reordered in a zigzag order, the coefficients for the lower frequencies are located relatively before those for higher frequencies in the reordered list of coefficients. Thus, non-zero coefficients are more likely to concentrate in the front portion of the reordered coefficient list; and zero coefficients are more likely to concentrate in the end portion of the reordered list.
Since compressing images is a computational intensive operation, it is desirable to have highly efficient methods and apparatuses to perform run length encoding and variable length encoding.
Methods and apparatuses for variable length encoding using a vector processing unit arc described here.
In one aspect of the invention, a method for execution by a microprocessor to perform variable length encoding including: receiving a plurality of parameters, each of the plurality of parameters corresponding to one of a plurality of symbols to be variable length encoded; generating concurrently a plurality of first codewords from the plurality of parameters to represent respectively the plurality of symbols; generating a plurality of lengths representing respectively bit lengths of the plurality of first codewords; and outputting the plurality of first codewvords and the plurality of lengths; where the above operations are perfonned in respionse to the microprocessor receiving a single instruction.
In one example according to this aspect, the plurality of parameters includes a plurality of indices; and to generate concurrently the plurality of first codewords, a plurality of entries are looked up simultaneously from a plurality of look up tables, which are configured from a plurality of look up units to function as the plurality of look up tables. Each of the look up tables utilizes more than one of the plurality of look up units. Each entry of the plurality of entries includes a first bit segment representing a second codeword and a second bit segment representing a bit length of the second codeword.
The plurality of parameters further includes a plurality ol sign indicators, each of which indicates the value of a sign bit of a corresponding one of the plurality of symbols. Each of the plurality of entries further includes a third bit segmnent indicating whether or not to append a sign bit of a corresponding one of the plurality of symbols. A sign bit of a first symbol in the plurality of symbols, which corresponds to a first entry in the plurality of entries, is appended to the second codeword represented by the first bit segment of the first entry when the third bit segment of the first entry indicates to append the sign bit.
The plurality of parameters further includes a plurality of type indicators for the plurality of symbols respectively; and the plurality of parameters and the plurality of entries are combined to generate the plurality of first codewords.
When one of the plurality of type indicators, which corresponds to a first symbol in the plurality of symbols, has a first value, a zero is generated as one of the plurality of first codewords to represent the first symbol.
The plurality of parameters further includes a plurality of third codewords, each of the plurality of third codewords corresponding to one of the plurality ofsymbols.
When one of the plurality of type indicators, which corrcsponds to a first symbol in the plurality of symbols, has a second value, one of the plurality of third codewords is used as one of the plurality of first codewords to represent the first symbol.
When one of the plurality of type indicators, which corresponds to a first symbol in the plurality of symbols, has a third value, one of the plurality of first codewords that represents the first symbol is generated from concateinating one of the plurality of third codewords that corresponds to the first symbol and the second codeword represented by the first bit segment of a first entry in the plurality of entries, which entry corresponds to the first symbol.
The present invention includes apparatuses which perfonn these methods, including data processing systems which perform these methods, and cmputer readable media which when executed on data processing systems cause the systems to perform these methods.
Other features of the present invention will be apparent from the accompanying drawings and from the detailed description which follow.